Background: Professionalism and communication skills constitute important components of the integral formation of physicians which has repercussion on the quality of health care and medical education. The objective of this study was to assess medical graduates’ professionalism and communication skills from the patients’ perspective and to examine its association with patients’ socio-demographic variables. Methods: This is a hospital based cross-sectional study. It involved 315 patients and 105 medical graduates selected by convenient sampling method. A modified and validated version of the American Board of Internal Medicine’s (ABIM) Patient Assessment survey questionnaire was used for data collection through a face to face interview. Data processing and analysis were performed using the Statistical Package for Social Science (SPSS) 16.0. Mean, frequency distribution, and percentage of the variables were calculated. A non-parametric Kruskal Wallis test was applied to verify whether the patients’ assessment was influenced by variables such as age, gender, education, at a level of significance, p ≤ 0.05. Results: Female patients constituted 46% of the sample, whereas males constituted 54%. The mean age was 36 ± 16. Patients’ scoring of the graduate’s skills ranged from 3.29 to 3.83 with a mean of 3.64 on a five-point Likert scale. Items assessing the “patient involvement in decision-making” were assigned the minimum mean values, while items dealing with “establishing adequate communication with patient” assigned the maximum mean values. Patients, who were older than 45 years, gave higher scores than younger ones (p < 0.001). Patients with higher education reported much lower scores than those with lower education (p = 0.003). Patients’ gender did not show any statistically significant influence on the rating level. Conclusion: Generally patients rated the medical graduates’ professionalism and communication skills at a good level. Patients’ age and educational level were significantly associated with the rating level.